package recursivecode;

/**
 * 功能描述:nqueue已安排 , 经典的回溯  N 皇后的排列问题
 * 2024/07/28
 *
 * @author ZhangYi
 */
public class NQueueArranged {


	public static void main(String[] args) {
		int N = 10;
		System.out.println(getNQueueArrangedNumber(N));
	}

	/**
	 * 获取nqueue排列 数量,
	 *
	 * @param N n
	 * @return int
	 * @author ZhangYi
	 */
	private static int getNQueueArrangedNumber(int N) {
		if (N == 0) {
			return 0;
		}
		int[] record = new int[N];
		return process(record, N, 0);
	}

	/**
	 * 流程
	 *
	 * @param record      记录
	 * @param N    		N 皇后的数量
	 * @param rowIndex 列索引
	 * @return int
	 * @author ZhangYi
	 */
	private static int process(int[] record, int N, int rowIndex) {
		if (rowIndex == N){
			return 1;
		}

		int result =0;
		for (int columnIndex = 0; columnIndex < N; columnIndex++) {
			if (!isValid(record,rowIndex,columnIndex)){
				record[rowIndex]  = columnIndex;
				result +=process(record,N,rowIndex+1);
			}
		}

		return result;
	}

	private static boolean isValid(int[] record, int rowIndex, int columnIndex) {
		// 已经确定的位置, K, record[K]
		// 即将要摆放的位置, rowIndex,columnIndex
		for (int K = 0; K < rowIndex; K++) {
			if (record[K] == columnIndex || Math.abs(rowIndex - K) == Math.abs(columnIndex - record[K])){
				return true;
			}
		}
		return false;
	}


}
